import os
import time
def print_towers(towers, step_count):
    """在控制台打印当前汉诺塔状态"""
    os.system('cls' if os.name == 'nt' else 'clear')
    max_height = max(len(towers['A']), len(towers['B']), len(towers['C']))
    # 打印标题和步骤计数
    print(f"汉诺塔状态 (步骤: {step_count})")
    print("=" * 60)
    # 从顶部开始打印
    for level in range(max_height - 1, -1, -1):
        row = ""
        for pole in ['A', 'B', 'C']:
            if level < len(towers[pole]):
                disk_size = towers[pole][level]
                # 创建磁盘可视化：居中显示
                disk_str = ' ' * (10 - disk_size) + '■' * disk_size * 2 + ' ' * (10 - disk_size)
                row += disk_str
            else:
                row += ' ' * 22
        print(row)
    # 打印柱子底座
    print("=" * 22 + "=" * 22 + "=" * 22)
    print(f"{'A':^22}{'B':^22}{'C':^22}")
    print("\n" + "-" * 60)

def move_disk(towers, source, target, step_count, delay=0.5):
    """移动磁盘并更新可视化"""
    if towers[source]:
        disk = towers[source].pop()
        towers[target].append(disk)
        step_count += 1
        print_towers(towers, step_count)
        time.sleep(delay)
    return step_count

def hanoi_visualized(n, source='A', target='C', auxiliary='B'):
    """带可视化的汉诺塔递归解法"""
    towers = {
        'A': list(range(n, 0, -1)),  # 初始：A柱有n个磁盘，从大到小
        'B': [],
        'C': []
    }
    step_count = 0
    print_towers(towers, step_count)
    time.sleep(1)
    def _hanoi(n, src, tgt, aux):
        nonlocal step_count
        if n > 0:
            _hanoi(n - 1, src, aux, tgt)
            step_count = move_disk(towers, src, tgt, step_count)
            _hanoi(n - 1, aux, tgt, src)
    _hanoi(n, source, target, auxiliary)
    return step_count
# 运行示例（3层汉诺塔）
total_steps = hanoi_visualized(3)
print(f"\n完成！总步数: {total_steps} (理论最小值: {2 ** 3 - 1})")